|
Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer. == Details of the algorithm == Suppose we have a permutation containing different elements. Heap found a systematic method for choosing at each step a pair of elements to switch, in order to produce every possible permutation of these elements exactly once. Let us describe Heap's method in a recursive way. First we set a counter ''i'' to 0. Now we perform the following steps repeatedly, until ''i'' is equal to ''N''. We use the algorithm to generate the (''N'' − 1) procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 0; i < n - 1; i += 1 do generate(n - 1, A) if n is even then swap(A(), A()) else swap(A(), A()) end if end for generate(n - 1, A) end if One could also write the algorithm in a non-recursive format.〔(【引用サイトリンク】first=Robert )〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Heap's algorithm」の詳細全文を読む スポンサード リンク
|